package main

import (
	"fmt"
	"gopl/ch5/traversal"
	"sort"
)

var prereqs = map[string][]string{
	"algorithms":     {"data structures"},
	"calculus":       {"linear algebra"},
	"linear algebra": {"calculus"},
	"compliers": {
		"data structures",
		"formal languages",
		"computer organization",
	},
	"data structures":       {"discrete math"},
	"databases":             {"data structures"},
	"discrete math":         {"intro to programming"},
	"formal languages":      {"discrete math"},
	"networks":              {"operating systems"},
	"operating systems":     {"data structures", "computer organization"},
	"programming languages": {"data structures", "computer organization"},
}

func main() {
	// for i, course := range topoSort(prereqs) {
	// 	fmt.Printf("%d:\t%s\n", i+1, course)
	// }
	// for i, course := range topoSort1(prereqs) {
	// 	fmt.Printf("%d:\t%s\n", i+1, course)
	// }
	// fmt.Println(hasCycle(prereqs))
	//广度优先遍历
	var order []string
	do := func(item string) []string {
		order = append(order, item)
		return prereqs[item]
	}
	var keys []string
	for key := range prereqs {
		keys = append(keys, key)
	}
	sort.Strings(keys)
	traversal.BreadthFirst(do, keys)
	fmt.Println(order)

}

// 深度优先拓扑
func topoSort(m map[string][]string) []string {
	var order []string
	seen := make(map[string]bool)
	var visitAll func(items []string)
	visitAll = func(items []string) {
		for _, item := range items {
			if !seen[item] {
				seen[item] = true
				visitAll(m[item])
				order = append(order, item)
			}
		}
	}
	var keys []string
	for key := range m {
		keys = append(keys, key)
	}
	sort.Strings(keys)
	visitAll(keys)
	return order
}

// 练习5.10: 重写topoSort函数，用map代替切片并移除对key的排序代码。验证结果的正确性 (结果不唯一)。
func topoSort1(m map[string][]string) []string {
	var order []string
	seen := make(map[string]bool)
	var visitAll func(items map[string]bool)
	visitAll = func(items map[string]bool) {
		for item, _ := range items {
			if !seen[item] {
				seen[item] = true
				visitAll(sliceToMap(m[item]))
				order = append(order, item)
			}
		}
	}
	keys := make(map[string]bool)
	for key := range m {
		keys[key] = true
	}
	visitAll(keys)
	return order
}

func sliceToMap(s []string) map[string]bool {
	m := make(map[string]bool)
	for _, v := range s {
		m[v] = true
	}
	return m
}

// 检测有向环 练习5.11: 现在线性代数的老师把微积分设为了前置课程。完善topSort，使其能检测有向图 中的环。
func hasCycle(m map[string][]string) bool {
	keda := make(map[string]map[string]bool)
	seen := make(map[string]bool)
	var visitAll func(items []string, p string)
	visitAll = func(items []string, p string) {
		for _, item := range items {
			if !seen[item] {
				seen[item] = true
				keda[p][item] = true
				visitAll(m[item], item)
			}
		}
	}

	for key := range m {
		keda[key] = make(map[string]bool)

	}
	for key := range m {
		visitAll(m[key], key)
	}

	for key := range keda {
		for k := range keda[key] {
			if keda[k][key] {
				return true
			}

		}
	}
	return false
}
